#include <math.h>
#include <time.h>

#include <unistd.h>

#include "hamiltonien.h"

/*
 * Fonction :    generateCoordonne
 * 
 * Parametres :  int** ligne (un pointeur sur le tableau d'entier)
 *							 int** col (un pointeur sur le tableau d'entie)
 *							 int nbSommet (le nombre maximum de sommets)
 *               int graine (la graine d'initialisation de la sequence alleatoire )
 *
 * Retour :      MAX_SOMMET_INVALIDE si le nombre maximum de sommets n'est pas valide
 *               RES_OK si le resultat est OK
 *
 * Description : initialisation aleatoire des coordonnes de sommets.
 * 
 * Complexité	:	O(n) - n le nombre de max de sommets
 */
int generateCoordonne(int** ligne, int** col, int nbSommet, int graine) {

	int i;

	// Si le nombre max de sommet n'est pas valide
	if (nbSommet <= 0) {
		return MAX_SOMMET_INVALIDE;
	}

	/* initialisation de la fonction random avec une graine */
	srandom((unsigned long) graine);

	for (i = 0; i < nbSommet; i++) {
		(*ligne)[i] = rand() % 100;
		(*col)[i] = rand() % 100;
	}

	return RES_OK;
}


/*
 * Fonction :    createGraph
 * 
 * Parametres :  Graphe** graphe (le pointeur sur le graphe)
 *							 int size (le nombre maximum de sommets)
 *
 * Retour :      MAX_SOMMET_INVALIDE si le nombre maximum de
 * 				sommets n'est pas valide
 *               RES_OK si le resultat est OK
 *
 * Description : creation de graphe complet
 * 
 * Complexité	:	O(n) - n le nombre de max de sommets
 */
int createGraph(Graphe** graph, int size, int graine) {

	// We need a graph with nothing in it.
	if ((*graph) !=  NULL) {
		printf("Attention, graph given is not null - createGraph\n");
		return GRAPHE_DEJA_EXISTANT;
	}

	// Verification of vertex size given
	if (size <= 0) {
		printf("Attention, graph vertex size "
				"is negative or null - createGraph\n");
		return MAX_SOMMET_INVALIDE;
	}

	/**
	 * Here graph is OK and vertex size is OK too.
	 * No verification required after these lines.
	 * Please don't remove.
	 */

	// To save (x, y) chosen randomly
	int *ligne = NULL, *col = NULL;


	// Memory allocation
	ligne = (int *) malloc (sizeof(int) * size);
	col = (int *) malloc (sizeof(int) * size);

	// Allocating verification
	if (ligne == NULL || col == NULL) {
		printf("Attention, memory problem on malloc - createGraph\n");
		return PROBLEME_MEMOIRE;
	}

	// Let's get generated coordinates
	int res = generateCoordonne(&ligne, &col, size, graine);

	// Let's create our graph
	res = creation(graph, size);

	// In case of memory problem
	if (res == PROBLEME_MEMOIRE) {
		printf("Attention, memory problem acquired - createGraph\n");
		return PROBLEME_MEMOIRE;
	}

	// Create all vertex needed from 0 to SIZE
	res = insertAllVertex(*graph);

	// In case of memory problem
	if (res == PROBLEME_MEMOIRE) {
		printf("Attention, memory problem acquired - createGraph\n");
		free(ligne); free(col);
		return PROBLEME_MEMOIRE;
	}

	// Complete graph, each vertex is connected with another one
	completeGraph(*graph, ligne, col);

	// Don't need any more
	free(ligne);
	free(col);

	return RES_OK;
}


/*
 * Function		:	completeGraph
 *
 * Authors		:	BAYRAMOV Matin
 *
 * Parameters	:	Graphe * graph - graph to fill with edges
 * 					int * line - array with x axe values
 * 					int * column - array with y axe values
 *
 * Return		:	GRAPHE_INEXISTANT - if graph does not exist
 * 					RES_OK - if it's OK.
 *
 * Description 	:	fill graph with full of edges, each vertex is
 * 					connected with another ones.
 *
 * Complexity	:	O(n2) - n is the number of vertex
 */
int completeGraph(Graphe *graph, int *line, int *column) {

	// Graph existence verification
	if (graph == NULL) {
		printf("Attention, graph given is null - completeGraph\n");
		return GRAPHE_INEXISTANT;
	}

	// Verification of given arrays
	if (line == NULL || column == NULL) {
		printf("Attention, line and column given is null - completeGraph\n");
		return -1;
	}

	int i, j, nbMaxSommet;
	double poids;

	nbMaxSommet = graph->nbMaxSommets;

	// For each vertex
	for (i = 0; i < nbMaxSommet; i++) {

		// For each vertex
		for (j = 0; j < nbMaxSommet; j++) {

			// Not the same vertexes
			if (i == j) { continue; }

			// Let's calculate the distance between these points
			poids = getEuclidieanDistance(line[i], column[i], line[j], column[j]);

			// Insert of new edge, will not effect if one is already exist.
			insertionArete(graph, i+1, j+1, poids, 'n');
		}
	}

	return RES_OK;
}


/*
 * Function		:	insertAllVertex
 *
 * Authors		:	BAYRAMOV Matin
 *
 * Parameters	:	Graphe * graph - graph to fill with vertices
 *
 * Return		:	GRAPHE_INEXISTANT - if graph does not exist
 * 					RES_OK - if it's OK.
 *
 * Description 	:	fill graph with it's number of vertex given
 *
 * Complexity	:	O(n) - n is the number of vertex to insert
 */
int insertAllVertex(Graphe* graph) {

	// Graph existence verification
	if (graph == NULL) {
		printf("Attention, graph given is null - insertAllVertex\n");
		return GRAPHE_INEXISTANT;
	}

	// Get the vertex number to fill graph
	int nbMaxSommets = graph->nbMaxSommets;

	int var;
	// For each vertex
	for (var = 1; var <= nbMaxSommets; var++) {
		// Insert it to graph
		int res = insertionSommet(graph, var);

		if (res == PROBLEME_MEMOIRE) {
			return PROBLEME_MEMOIRE;
		}
	}

	return RES_OK;
}

/*
 * Function		:	getEuclidieanDistance
 *
 * Authors		:	BAYRAMOV Matin
 *
 * Parameters	:	int (x0, y0) & int (x1, y1) - points
 *
 * Return		:	double distance -
 *
 * Description 	:	calculate the euclidiean distance between these
 * 					two points
 *
 * Complexity	:	O(1)
 */
double getEuclidieanDistance(int x0, int y0, int x1, int y1) {

	double distance = 0.0;

	distance = (x0 - x1) * (x0 - x1) + (y0 - y1) * (y0 - y1);

	distance = sqrt(distance);

	return distance;
}

